#include <atomic>
#include <memory>

template<typename T>
class LockFreeQueue {
private:
    struct Node {
        std::shared_ptr<T> data;
        std::atomic<Node*> next;

        Node() : next(nullptr) {}
    };

    std::atomic<Node*> head;
    std::atomic<Node*> tail;

public:
    LockFreeQueue() {
        Node* dummy = new Node();
        head.store(dummy);
        tail.store(dummy);
    }

    ~LockFreeQueue() {
        while (Node* old_head = head.load()) {
            head.store(old_head->next);
            delete old_head;
        }
    }

    // 禁止拷贝和赋值
    LockFreeQueue(const LockFreeQueue&) = delete;
    LockFreeQueue& operator=(const LockFreeQueue&) = delete;

    void push(T new_value) {
        std::shared_ptr<T> new_data(std::make_shared<T>(std::move(new_value)));
        Node* new_node = new Node();
        new_node->data = new_data;
        
        Node* current_tail = nullptr;
        Node* current_next = nullptr;
        
        while (true) {
            current_tail = tail.load(std::memory_order_acquire);
            current_next = current_tail->next.load(std::memory_order_acquire);
            
            // 检查tail是否被其他线程修改
            if (current_tail != tail.load(std::memory_order_relaxed)) 
                continue;
            
            // 如果tail指向的不是最后一个节点
            if (current_next != nullptr) {
                // 尝试更新tail到真正的尾节点
                tail.compare_exchange_weak(
                    current_tail, 
                    current_next,
                    std::memory_order_release,
                    std::memory_order_relaxed
                );
                continue;
            }
            
            // 尝试将新节点添加到链表尾部
            if (current_tail->next.compare_exchange_weak(
                current_next, 
                new_node,
                std::memory_order_release,
                std::memory_order_relaxed
            )) {
                break;
            }
        }
        
        // 尝试更新tail指向新节点
        tail.compare_exchange_weak(
            current_tail, 
            new_node,
            std::memory_order_release,
            std::memory_order_relaxed
        );
    }

    bool pop(T& value) {
        Node* current_head = nullptr;
        Node* current_tail = nullptr;
        Node* current_next = nullptr;
        
        while (true) {
            current_head = head.load(std::memory_order_acquire);
            current_tail = tail.load(std::memory_order_acquire);
            current_next = current_head->next.load(std::memory_order_acquire);
            
            // 检查head是否被其他线程修改
            if (current_head != head.load(std::memory_order_relaxed))
                continue;
            
            // 队列为空
            if (current_head == current_tail) {
                if (current_next == nullptr) {
                    return false; // 空队列
                }
                // 帮助推进tail
                tail.compare_exchange_weak(
                    current_tail,
                    current_next,
                    std::memory_order_release,
                    std::memory_order_relaxed
                );
            } else {
                // 读取数据
                value = std::move(*current_next->data);
                
                // 尝试移动head到下一个节点
                if (head.compare_exchange_weak(
                    current_head,
                    current_next,
                    std::memory_order_release,
                    std::memory_order_relaxed
                )) {
                    break;
                }
            }
        }
        
        // 删除旧头节点
        delete current_head;
        return true;
    }

    bool empty() const {
        return head.load(std::memory_order_acquire) == 
               tail.load(std::memory_order_acquire);
    }
};